class Solution {
    boolean[][] row;
    boolean[][] col;
    boolean[][][] grid;

    public void solveSudoku(char[][] board) {
        row = new boolean[9][10];
        col = new boolean[9][10];
        grid = new boolean[3][3][10];

        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] != '.'){
                    int num = board[i][j] - '0';
                    row[i][num] = true;
                    col[j][num] = true;
                    grid[i / 3][j / 3][num] = true;
                }
            }
        }
        dfs(board);
    }
    public boolean dfs(char[][] board){
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] == '.'){
                    // 设置一个1~9的数字
                    for(int k = 1; k <= 9; k++){
                        // 选一个合法的数字 - 剪枝方法
                        if(row[i][k] == false && col[j][k] == false && grid[i / 3][j / 3][k] == false){
                            board[i][j] = (char)('0' + k);
                            row[i][k] = true;
                            col[j][k] = true;
                            grid[i / 3][j / 3][k] = true;
                            if(dfs(board) == false){
                                // 回溯
                                board[i][j] = '.';
                                row[i][k] = false;
                                col[j][k] = false;
                                grid[i / 3][j / 3][k] = false;
                            }else{
                                return true;
                            }
                        }
                    }
                    return false;
                }
            }
        }
        // 递归出口 - 所有数字都填上了
        return true;
    }
}